import java.util.Arrays;

public class Solution_435 {
    /**
     * 方法一：暴力的递归
     * @param intervals
     * @return
     */
//    public int eraseOverlapIntervals(int[][] intervals) {
//        //按照起始时间排序
//        Arrays.sort(intervals,(i1,i2) -> Integer.compare(i1[0],i2[0]));
//        //递归
//        return eraseOverlapIntervals(-1,0,intervals);
//    }

    /**
     * 返回最少需要删除的区间数
     * @param pre 前一个区间下标
     * @param curr  当前区间下标
     * @param intervals 区间数组
     * @return 要删除的最小区间数
     */
    int eraseOverlapIntervals(int pre,int curr,int[][] intervals){
        if (curr == intervals.length) {
            return 0;
        }
        //taken表示删除当前区间时最少需要删除多少其他区间，nottaken表示不删除当前区间的情况
        int taken = Integer.MAX_VALUE,nottaken;

        //第一个区间
        if (pre == -1 || intervals[pre][1] <= intervals[curr][0]) {
            //未发生重叠，不删除
            taken = eraseOverlapIntervals(curr,curr+1,intervals);
        }

        //其他情况，考虑如果删除该区间
        nottaken = eraseOverlapIntervals(pre,curr+1,intervals) + 1;

        return Math.min(taken,nottaken);
    }

    /**
     * 方法二
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        //极端情况
        if (intervals.length == 0) {
            return 0;
        }

        //按起始时间进行排序
        Arrays.sort(intervals,(i1,i2) -> Integer.compare(i1[0],i2[0]));

        //初始化end，即当前最小结束时间。初始化要删除的区间数
        int end = intervals[0][1],count = 0;

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                //发生重叠，则表示要删除结束时间最常的且更新end
                end = Math.min(end,intervals[i][1]);
                count++;
            }else {
                end  = intervals[i][1];
            }
        }

        return count;
    }
}
